1. Field
The present technology relates to interleavers. More particularly, the technology relates to an interleaver with a low memory footprint suitable for use in digital communication systems.
2. Description of the Related Art
In digital communications, interleaving is used as a component in iterative forward error correction (FEC) coding algorithms. Interleavers are used to re-order the bits of a data block to help increase the performance of such FEC coding algorithms. Generally, an interleaver maps a bit or symbol position of an input data block to another bit or symbol position in an output data block. Conventional interleavers used in such FEC coding algorithms include pseudo-random interleavers and algorithmic (structured) interleavers.
Conventionally, pseudo-random interleavers are generated using a pseudo-random number generator under certain constraints. One example of such a pseudo-random interleaver is an “S-random” interleaver as described in the publication by S. Dolinar and D. Divsalar, “Weight Distribution for Turbo Codes Using Random and Nonrandom Permutations,” JPL Progress Report 42-122, pp. 56-65, Aug. 15, 1995. In an S-random interleaver, “S” may be any positive integer value. A pseudo-random number generator is used to generate numbers to be selected or discarded as indexes for the interleaver sequence of length K, where K is a positive integer corresponding to the length of the blocks being re-ordered. Each generated number is either selected as the next index for the interleaver sequence, or discarded until K integers are selected. Each generated number is compared to the previous S values (or fewer if there are not S previous values) selected as part of the interleaver sequence. If the generated number has a value that is within +/−S of any of the previous S indexes selected in the interleaver sequence, the generated number is discarded. Otherwise, the generated number is selected as the next index for the interleaver sequence.
The search time for selecting a number as the next index for the interleaver sequence increases as the value of S increases. Further, there is no guarantee that the pseudo-random number generator will generate numbers for the interleaver sequence that satisfy the S constraint. Accordingly, generation of such interleaver sequences for S-random interleavers and similar pseudo-random interleavers is time consuming and therefore is not performed on the fly during data encoding/decoding. Thus, once an interleaver sequence is successfully generated, the interleaver sequence is stored in a lookup-table based architecture for use during data encoding/decoding. FIG. 1A is a flowchart illustrating a process of generating such a lookup table for a pseudo-random interleaver. As shown, index values are generated, and if they meet the criteria for an interleaver (e.g., satisfy the S constraint), the index values are stored. An interleaver using such a lookup-table arranges data according to the stored sequence. FIG. 1B is a flowchart illustrating a process of operating a pseudo-random interleaver that uses values stored in a lookup table. As shown, bits are moved based on the index values contained in the lookup table. These lookup tables require large amounts of storage in memory to store each individual index of the pseudo-random interleaver. However, pseudo-random interleavers provide good performance levels and construction is of relatively low complexity.
Conventional algorithmic interleavers are defined by a generation algorithm and a set of algorithm parameters. Such algorithms are capable of being run in real time. Further, such algorithms and parameters require less storage in memory than the lookup table of a pseudo-random interleaver. An interleaver using such algorithms arranges data according to the sequence of algorithm outputs. FIG. 1C is a flowchart illustrating a process of operating an algorithmic interleaver. As shown, bits are moved based on the index location generated by an algorithm. Examples of algorithmic interleavers are dithered relative prime interleavers and quadratic permutation polynomial interleavers. Although algorithmic interleavers provide memory efficiencies that may be useful for high volume communication equipment manufacturers (e.g., mobile phone manufacturers), the interleaver sequences they produce generally perform poorer as compared to S-random interleavers.